package gold.digger;

import gold.vo.TreeNode;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC124 {


    int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        oneSideMax(root);
        return ans;
    }

    public int oneSideMax(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = Math.max(0, oneSideMax(root.left));
        int right = Math.max(0, oneSideMax(root.right));
        ans = Math.max(ans, left + right + root.val);
        return Math.max(left, right) + root.val;
    }


    public static void main(String[] args) {
        LC124 an = new LC124();
    }
}
